package com.xiyou.week06.greedy;

import java.util.Arrays;

/**
 * 1665. 完成所有任务的最少初始能量
 *
 * @ClassName：MinimumEffort
 * @Author：西柚
 * @Date：2022/2/24 4:01 下午
 * @Versiion：1.0
 */
public class MinimumEffort {

    /**
     * 输入：tasks = [[1,2],[2,4],[4,8]]
     * 输出：8
     * 解释：
     * 一开始有 8 能量，我们按照如下顺序完成任务：
     * - 完成第 3 个任务，剩余能量为 8 - 4 = 4 。
     * - 完成第 2 个任务，剩余能量为 4 - 2 = 2 。
     * - 完成第 1 个任务，剩余能量为 2 - 1 = 1 。
     * 注意到尽管我们有能量剩余，但是如果一开始只有 7 能量是不能完成所有任务的，因为我们无法开始第 3 个任务。
     *
     * @param tasks
     * @return
     */
    public int minimumEffort(int[][] tasks) {
        Arrays.sort(tasks, (a, b) -> {
            return a[0] - a[1] - b[0] + b[1];
        });
        int ans = 0;
        for (int i = tasks.length - 1; i >= 0; i--) {
            ans = Math.max(tasks[i][1], ans + tasks[i][0]);
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] tasks = new int[][]{{1, 2}, {2, 4}, {4, 8}};
        MinimumEffort minimumEffort = new MinimumEffort();
        System.out.println(minimumEffort.minimumEffort(tasks));
    }

}
